package com.gorkr.nsum;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;


/**
 *
 */
public class M15ThreeSum {

    public List<List<Integer>> threeSum(int[] nums) {

        Arrays.sort(nums);

        // 这个怎么优化？
        ArrayList<Integer> trace = new ArrayList<>(3);
        trace.add(0);
        trace.add(0);
        trace.add(0);

        LinkedList<List<Integer>> res = new LinkedList<>();


        for (int i = 0; i < nums.length; i++) {
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            int sum = -nums[i];
            while (left < right) {
                int now = nums[left] + nums[right];
                if (now == sum) {
                    ArrayList<Integer> item = new ArrayList<>();
                    item.add(nums[i]);
                    item.add(nums[left]);
                    item.add(nums[right]);
                    res.add(item);
                    //todo
                    left++;
                    while (left<right&&nums[left-1]==nums[left]){
                        left++;
                    }
                    right--;
                    while (left<right&&nums[right]==nums[right+1]){
                        right--;
                    }

                }else if(now < sum){
                    left++;
                    while (left<right&&nums[left-1]==nums[left]){
                        left++;
                    }
                }else {
                    right--;
                    while (left<right&&nums[right+1]==nums[right]){
                        right--;
                    }
                }

            }
        }
        return res;
    }

    @Test
    public void test(){
        int[] nums = {-1,0,1,2,-1,-4};
        System.out.println(threeSum(nums).toString());
    }
}
